package Demo3;

/**
 * @ClassName DoublyLinkedList
 * @Description 双向链表操作
 * @Author ZJX
 * @Date 2024/9/17 20:32
 * @Version 1.0
 */
public class DoublyLinkedList {
    static class LinkedNode {
        private int val;
        private LinkedNode prior;
        private LinkedNode next;
        private int freq; // 访问频度域

        public LinkedNode(int val) {
            this.val = val;
            this.prior = null;
            this.next = null;
            this.freq = 0;
        }
    }

    private LinkedNode head; // 头结点
    private LinkedNode tail; // 尾结点

    public DoublyLinkedList() {
        head = null;
        tail = null;
    }

    public LinkedNode locate(int x) {
        LinkedNode cur = head;

        // 查找值为 x 的结点
        while (cur != null && cur.val != x) {
            cur = cur.next;
        }

        // 如果没有找到结点，直接返回
        if (cur == null) {
            System.out.println("节点 " + x + " 不存在");
            return null;
        }

        // 找到结点，访问频度加 1
        cur.freq++;

        // 维护链表按 freq 递减顺序排列

        // 如果当前结点已经在表头，或者它的频率比前一个结点的频率小，则无需移动
        if (cur == head || cur.freq <= cur.prior.freq) {
            return cur;
        }

        // 将当前结点从链表中移除
        if (cur.prior != null) {
            cur.prior.next = cur.next;
        }

        if (cur.next != null) {
            cur.next.prior = cur.prior;
        }

        // 如果当前结点是尾结点，更新 tail
        if (cur == tail) {
            tail = cur.prior;
        }

        // 重新插入到链表中的正确位置（按照 freq 递减的顺序）
        LinkedNode temp = cur.prior;
        while (temp != null && temp.freq < cur.freq) {
            temp = temp.prior;
        }

        // 找到位置  将 cur 插入到 temp 后面
        if (temp == null) {
            // 插入到链表头部
            cur.next = head;
            if (head != null) {
                head.prior = cur;
            }
            head = cur;
            cur.prior = null;
        } else {
            // 插入到 temp 后面
            cur.next = temp.next;
            if (temp.next != null) {
                temp.next.prior = cur;
            }
            temp.next = cur;
            cur.prior = temp;
        }

        // 如果 cur 是新的尾结点
        if (cur.next == null) {
            tail = cur;
        }

        return cur;
    }


    // 插入节点到链表尾部
    public void insert(int x) {
        LinkedNode newNode = new LinkedNode(x);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prior = tail;
            tail = newNode;
        }
    }


    // 打印链表的值和频度
    public void printList() {
        LinkedNode current = head;
        while (current != null) {
            System.out.println("值: " + current.val + ", 频度: " + current.freq);
            current = current.next;
        }
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();

        // 初始化链表为 1, 2, 3, 4, 5, 6
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        list.insert(6);

        System.out.println("初始链表:");
        list.printList();

        // 访问频度更新
        list.locate(3); // 访问 3，频度变为 1
        list.locate(5); // 访问 5，频度变为 1
        list.locate(3); // 再次访问 3，频度变为 2

        System.out.println("访问后链表:");
        list.printList();
    }
}
